package 动态规划.背包And分组And切割问题系列;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/6/25 21:12
 */
public class lc1723最小工作时间 {
    /*
     这个题， 展示 了 另外的一个问题， 就是
     把一个数组分成 k 份（并没有要求 连续， 也就是，  并不是之前的那种把一个 数组 分成 k 个连续的子数组的问题，
     这是另外的一个版本！）
     */



    /*
     如果 说 至多 分成 k组, 一般 去临界值 k , 是可以取得最优的结果的
     - 比如 该题: 分给 k 个工人 , 工人越多, 那么完成 工作所需要的时候 也是越少的, 这是一个很明显的一个贪心策略

     这种题的 , f() 函数的一个 含义 怎么去定义 ?
     */
    public int recursion(int k,boolean []used,int []jobs){
        /*
         必须 分成 k 组, 而且 不能有 元素没有被分组!
         有两种 判断方式:
         - 1. 元素被分完之后, 是否 分组 达到 k 组
         - 2. k = 0 时, 也就是 分成 k 组之后, 是否还有元素没有被分配

         - 对于 该题而言 : 判断是否 分成 k 组 非常的简单  k == 0 就代表已经被分成k 组
         */
        if(k == 0 && judgeElementSplit(used)){
            return 0;
        }

        for(int i = 0;i < jobs.length;i++){
            if(!used[i]){
                // 分到 当前 编号为 k 的这组
                recursion(k - 1,used,jobs);
                // 跳过 编号为 k 的组
            }
        }


        return 0;
    }
    /*
    如果所有的元素, 都被使用过, 那说明就已经所有元素 都参与分配了!
     */
    public boolean judgeElementSplit(boolean used[]){
        int count = 0 ;  // thos  variable 都用不到!
        for(int i = 0;i < used.length;i++){
            if(!used[i]){
                return false;
            }
        }
        return true;
    }


}
